import { log } from "console";
import { ListNode } from "../../const";

/**
 * @name 347.前K个高频元素
 * @link https://leetcode.cn/problems/top-k-frequent-elements/
 */
function topKFrequent(nums: number[], k: number): number[] {
  let ans: number[] = [];
  let dict: { [key: string]: number } = {};
  for (let i = 0; i < nums.length; i++) {
    if (dict.hasOwnProperty(nums[i])) {
      dict[nums[i]] += 1;
    } else {
      dict[nums[i]] = 1;
    }
  }
  let tmp = Object.keys(dict)
    .sort((a, b) => dict[b] - dict[a])
    .map((i) => Number(i));
  ans = tmp.splice(0, k);

  console.log(ans);

  return ans;
}

/**
 * @name 692.前K个高频单词
 * @link https://leetcode.cn/problems/top-k-frequent-words/description/
 */
function topKFrequentWords(words: string[], k: number): string[] {
  let ans: string[] = [];
  let dict: { [key: string]: number } = {};
  for (let i = 0; i < words.length; i++) {
    if (dict.hasOwnProperty(words[i])) {
      dict[words[i]] += 1;
    } else {
      dict[words[i]] = 1;
    }
  }
  let tmp = Object.keys(dict).sort((a, b) => dict[b] - dict[a]);
  let sortTmp: string[] = [];
  // 处理不同字符同数量字典序
  let start = 0;
  let flag = dict[tmp[0]];
  for (let i = 0; i < tmp.length; i++) {
    if (flag === dict[tmp[i]]) {
      sortTmp.push(tmp[i]);
    } else {
      sortTmp = sortTmp.sort();
      tmp.splice(start, sortTmp.length, ...sortTmp);
      sortTmp = [tmp[i]];
      start = i;
      flag = dict[tmp[i]];
    }
  }
  sortTmp = sortTmp.sort();
  tmp.splice(start, sortTmp.length, ...sortTmp);

  ans = tmp.splice(0, k);
  console.log(ans);

  return ans;
}

/**
 * @name 1163.按字典序排在最后的子串
 * @link https://leetcode.cn/problems/last-substring-in-lexicographical-order/description/
 */
function lastSubstring(s: string): string {
  if (s.length === 0) return "";
  let ans: string = "";
  // const greaterThan = (a: string, b: string) => {
  //   let cmp = 0;
  //   while (cmp < Math.min(a.length, b.length)) {
  //     if (a[cmp] < b[cmp]) return false;
  //     cmp++;
  //   }

  //     return true;
  //   };
  //   const backtrack = (pos: number, str: string) => {
  //     if (pos >= s.length) return;

  //     str += s[pos];
  //     // console.log(str);
  //     if (greaterThan(str, ans)) {
  //       //   console.log(str, "greater than previous: ", ans);
  //       ans = str;
  //     } else {
  //       return;
  //     }
  //     backtrack(pos + 1, str);
  //   };
  //   for (let i = 0; i < s.length; i++) {
  //     backtrack(i, "");
  //   }
  //   console.log(ans);
  //   const compareStrings = (p1: number, p2: number, l: number) => {
  //     let a = p1 + 1;
  //     let b = p2 + 1;
  //     let len = 0;

  //     while (a < s.length && b < s.length) {
  //       if (s[a] < s[b]) {
  //         return [p2, p2 + 1, s.length - p2];
  //       }
  //       if (s[a] > s[b]) {
  //         return [p1, p2 + 1, l];
  //       }
  //       a++;
  //       b++;
  //       len++;
  //     }
  //     return [p1, p2 + 1, l];
  //   };
  //   let point1 = 0;
  //   let point2 = 1;
  //   let len = s.length;
  //   while (point2 < s.length) {
  //     if (s[point2] > s[point1]) {
  //       point1 = point2;
  //       len = s.length - point1;
  //       point2 += 1;
  //     }
  //     if (s[point2] === s[point1]) {
  //       if (s[point2 - 1] === s[point1]) {
  //         point2++;
  //         continue;
  //       }
  //       [point1, point2, len] = compareStrings(point1, point2, len);
  //       //   console.log(point1, point2, len, s.slice(point1, len + point1));
  //     }
  //     if (s[point2] < s[point1]) {
  //       point2 += 1;
  //     }
  //   }

  //   console.log(point1, len, s.slice(point1, len + point1));

  return ans;
}

/**
 * @name 206.反转链表
 * @link https://leetcode.cn/problems/reverse-linked-list/description/
 */
function reverseList(head: ListNode | null): ListNode | null {
  if (!head) return null;
  let tmp = head as ListNode | null;
  let list = [];
  while (tmp) {
    list.push(tmp);
    tmp = tmp.next;
  }
  for (let i = list.length - 1; i > 0; i--) {
    list[i].next = list[i - 1];
  }
  list[0].next = null;
  console.log(list[list.length - 1]);

  return list[list.length - 1];
}

/**
 * @name 146.LRU缓存
 * @link https://leetcode.cn/problems/lru-cache/description/
 */

/**
 * @name 三数之和
 * @link https://leetcode.cn/problems/3sum/description/
 */
function threeSum(nums: number[]): number[][] {
  // const ans: number[][] = [];

  // nums = nums.sort((a, b) => a - b);
  // const backtrack = (pos: number) => {
  //   // console.log(pos, tmp, tmpList, last);
  //   if (tmpList.length === 3) {
  //     // console.log(pos, tmp, tmpList);
  //     if (tmp === 0) {
  //       ans.push([...tmpList]);
  //     }
  //     tmp -= tmpList[tmpList.length - 1];
  //     last = tmpList[tmpList.length - 1];
  //     tmpList.pop();
  //     return tmp >= 0 ? true : false;
  //   }
  //   for (let i = pos + 1; i < nums.length; i++) {
  //     if (last === nums[i] && nums[i] === nums[i - 1]) continue;
  //     tmpList.push(nums[i]);
  //     tmp += nums[i];
  //     let flag = backtrack(i);
  //     if (flag) {
  //       break;
  //     }
  //   }
  //   tmp -= tmpList[tmpList.length - 1];
  //   last = tmpList[tmpList.length - 1];
  //   tmpList.pop();
  // };

  // let tmpList: number[] = [];
  // let tmp: number = 0;
  // let last: number | undefined = undefined;
  // for (let i = 0; i < nums.length; i++) {
  //   if (last === nums[i] && nums[i] === nums[i - 1]) continue;
  //   if (nums[i] > 0) break;
  //   tmpList.push(nums[i]);
  //   tmp += nums[i];
  //   backtrack(i);
  // }
  // console.log(ans);
  const ans: number[][] = [];
  nums = nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > 0) {
      break;
    }
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let start = i + 1;
    let end = nums.length - 1;
    while (start < end) {
      if (nums[i] + nums[start] + nums[end] === 0) {
        ans.push([nums[i], nums[start], nums[end]]);
        while (start < end && nums[start] === nums[start + 1]) {
          start += 1;
        }
        while (start < end && nums[end] === nums[end - 1]) {
          end -= 1;
        }
        start += 1;
        end -= 1;
      } else if (nums[i] + nums[start] + nums[end] > 0) end -= 1;
      else start += 1;
    }
  }

  console.log(ans);

  return [];
}

/**
 * @name LRU缓存
 * @link
 */
class LRUCache {
  capacity: number;
  queue: { key: number; value: number }[];
  constructor(capacity: number) {
    this.capacity = capacity;
    this.queue = [];
  }

  get(key: number): number {
    let target = this.queue.find((item) => item.key === key);

    if (target) {
      this.queue = this.queue.filter((item) => item.key !== key);
      this.queue.push(target);
      console.log([...this.queue], target);
      return target.value;
    }
    return -1;
  }

  put(key: number, value: number): void {
    let target = this.queue.find((item) => item.key === key);
    if (target) {
      this.queue = this.queue.filter((item) => item.key !== key);
      this.queue.push(target);
      target.value = value;
    } else {
      if (this.queue.length >= this.capacity) {
        this.queue.splice(0, 1);
      }
      this.queue.push({ key, value });
    }
    console.log([...this.queue]);
  }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

/**
 * @name 最长回文串
 * @link
 */
function longestPalindrome(s: string): number {
  let dict: { [key: string]: number } = {};
  for (let i = 0; i < s.length; i++) {
    if (dict.hasOwnProperty(s[i])) {
      dict[s[i]] += 1;
    } else {
      dict[s[i]] = 1;
    }
  }

  let maxOdd = 0;
  let ans = 0;
  let total = 0;

  console.log(dict);

  Object.keys(dict).map((key) => {
    total += dict[key];
    if (dict[key] % 2 === 0) {
      ans += dict[key];
    } else {
      maxOdd = 1;
      ans += dict[key] - 1;
    }
  });

  console.log(maxOdd, ans, total);

  ans += maxOdd;

  console.log(ans);

  return ans;
}

const combine = (n: number, k: number): number[][] => {
  const ans: number[][] = [];
  const backtrack = (pos: number, tmp: number[]) => {
    tmp.push(pos);
    console.log(pos, tmp);
    if (tmp?.length === k) {
      ans.push([...tmp]);
      return;
    }
    if (pos > n) {
      return;
    }

    for (let i = pos + 1; i <= n; i++) {
      backtrack(i, tmp);
      tmp.pop();
      console.log(pos, tmp, "end");
    }
  };

  for (let i = 1; i <= n - k + 1; i++) {
    console.log(i, "---------");

    backtrack(i, []);
  }
  console.log(ans);

  return [];
};

export default {
  topKFrequent,
  topKFrequentWords,
  lastSubstring,
  reverseList,
  threeSum,
  LRUCache,
  longestPalindrome,
  combine,
};
